import entity.TreeNode;

import java.util.LinkedList;

public class FindBottomLeftValue {
    /*
    * 513. 找树左下角的值
    * 给定一个二叉树的 根节点 root，请找出该二叉树的 最底层 最左边 节点的值。
    * 假设二叉树中至少有一个节点。
    *
    * 二叉树的节点个数的范围是 [1,10^4]
    * -2^31 <= Node.val <= 2^31 - 1
    * */
    public static void main(String[] args){

    }

    // 我的想法：递归，深度优先，先序遍历
    int depth = 0;
    int res;
    public int mySolution(TreeNode root){
        traversal(root, 1);
        return res;
    }
    private void traversal(TreeNode root, int deep){
        if(root == null)
            return;
        if(deep > depth){
            depth = deep;
            if(root.left == null && root.right == null) {
                res = root.val;
                return;
            }
        }
        traversal(root.left, deep+1);
        traversal(root.right, deep+1);
        return;
    }

    // 迭代法，层序遍历, 当然，开销比递归大就是了
    public int mySolution2(TreeNode root){
        int result = 0;
        LinkedList<TreeNode> deque = new LinkedList<>();
        deque.add(root);
        while (!deque.isEmpty()){
            int size = deque.size();
            for (int i = 0; i < size; i++) {
                root = deque.pop();
                if(i == 0)
                    result = root.val;
                if(root.left != null)
                    deque.add(root.left);
                if(root.right != null)
                    deque.add(root.right);
            }
        }
        return result;
    }
}
